package mpp;

import java.util.concurrent.locks.ReentrantLock;

class LazyQueue<T> implements PQueue<T>{
	private volatile LazyNode<T> head;
	
	public LazyQueue(){
		super();
		head = new LazyNode<T>(null, Integer.MIN_VALUE);
		head.next = new LazyNode<T>(null, Integer.MAX_VALUE);
	}
	
	@Override
	public void add(T item, int score) {
		while (true) {
			LazyNode<T> pred = head;
			LazyNode<T> curr = head.next;
			while (curr.key < score) {
				pred = curr;
				curr = curr.next;
			}
			pred.lock();
			try {
				curr.lock();
				try {
					if (validate(pred, curr)) {
						if (curr.key == score) {
							return;
						} else {
							LazyNode<T> node = new LazyNode<T>(item, score);
							node.next = curr;
							pred.next = node;
							return;
						}
					}
				} finally {
					curr.unlock();
				}
			} finally {
				pred.unlock();
			}
		}

	}
	
	

	@Override
	public T removeMin() {
		while (true) {
			LazyNode<T> pred = head;
			LazyNode<T> curr = head.next;
			while (curr.marked) {
				pred = curr;
				curr = curr.next;
			}
			pred.lock();
			try {
				curr.lock();
				try {
					if (validate(pred, curr)) {
						if (curr.key ==  Integer.MAX_VALUE) {
							return null;
						} else {
							curr.marked = true;
							pred.next = curr.next;
							return curr.value;
						}
					}
				} finally {
					curr.unlock();
				}
			} finally {
				pred.unlock();
			}
		}
	}
	
	private boolean validate(LazyNode<T> pred, LazyNode<T> curr) {
		return !pred.marked && !curr.marked && pred.next == curr;
		}
	
	@SuppressWarnings({ "hiding", "serial" })
	private class LazyNode<T> extends ReentrantLock{
		T value;
		int key = -1;
		LazyNode<T> next;
		boolean marked;

		LazyNode(T newValue, int key) {
			value = newValue;
			this.key = key;
			next = null;
			marked = false;
		}
	}

}
